Module: ESM이 순환참조를 해결하는 방법 - 위상정렬과 SCC

ECMAScript Module(ESM)은 브라우저와 Node.js 모두에서 정적 구조를 기반으로 동작하는 모듈 시스템이다. 정적 import/export를 가진 구조 때문에 로더는 모듈을 실행하기에 앞서 전체 의존성을 분석할 수 있다.

이 분석 과정에서 어떤 알고리즘이 사용되는지 궁금해서 찾아본 내용이다.

// main.js
import { foo } from './foo.js';

console.log(foo);

브라우저나 Node.js의 ESM 로더는 다음 단계를 거친다.

  1. Parsing
    • 브라우저가 main.js를 파싱하면서 import './foo.js'를 발견한다.
    • 로더는 즉시 foo.js를 fetch하고, 다시 그 안의 import를 DFS로 탐색한다.
    • 이 과정에서 전체 모듈을 병렬로 가져오며 의존성 그래프를 생성한다.
  2. Linking
    • 모듈 간 변수·함수 등의 바인딩을 연결한다.
    • 이 연결은 값 복사가 아니라 참조(live binding) 로 유지된다.
  3. Evaluation
    • 의존성 그래프를 기준으로 모듈 초기화 순서를 결정한다.
    • 이 단계에서 위상정렬(Topological Sort) 이 사용된다.
    • 함수 정의, 변수 초기화 등 모듈의 실제 실행이 이루어진다.
  4. Entry point 실행
    • 모든 모듈이 평가된 뒤 진입점(main.js)이 실행된다.

DFS를 활용하여, 의존성 그래프 만들기

ESM은 정적 import/export만 허용한다. 이를 통해 로더는 파싱 단계에서 바로 import 목록을 알 수 있다.

의존성 그래프 생성 과정에서 DFS는 다음 역할을 수행한다.

  1. 모듈 파일을 하나 읽을 때마다 import 문을 분석한다.
  2. 새로 발견한 모듈을 DFS로 재귀 탐색한다.
  3. 이 탐색을 통해 모든 모듈을 가져오고, 노드(파일)와 간선(import 관계)이 기록된다.
  4. 동시에 네트워크 fetch는 병렬로 수행된다.

여기서 DFS의 목적은 탐색과 그래프 구성이다. DFS는 “실행 순서”를 만드는 알고리즘이 아니다.
실행 순서는 아래에서 설명할 위상정렬의 역할이다.

위상정렬(Topological Sort)로 모듈 평가하기

Evaluation 단계는 “모듈을 어떤 순서로 초기화할 것인가”를 결정해야 한다. 모듈이 초기화되기 전에 다른 모듈이 그 값을 참조하면 안 되기 때문에 의존 관계를 위배하지 않는 순서가 필요하다.

DFS는 탐색 목적의 알고리즘이며 순환 구조가 있을 경우 무한 루프에 빠질 수 있다. 반면 위상정렬은 DAG(사이클 없는 방향 그래프) 에서 실행 순서를 만들기 위한 알고리즘이다. 문제는 ESM은 순환 참조를 금지하지 않는다는 점이다. 따라서 그래프에 사이클이 존재할 수 있으며 일반적인 위상정렬은 실패하게 된다. ESM은 이걸 어떻게 해결할까 ?

순환참조 문제는 SCC(Strongly Connected Component)로 해결

ESM의 모듈 그래프는 방향 그래프이며, 순환 참조가 존재할 수 있다. 순환을 허용하면서도 정상적으로 평가 순서를 만들기 위해 로더는 SCC(Strongly Connected Component) 를 이용한다. SCC의 핵심은 싸이클을 하나의 컴포넌트로 묶는 것이다.

SCC를 이용하면 다음과 같은 처리가 가능하다.

  • 순환 참조 구간을 하나의 큰 노드로 본다.
  • 전체 그래프를 SCC 단위로 압축하면 DAG가 된다.
  • DAG에 대해 위상정렬을 수행할 수 있다.

즉, 순환이 있는 그래프를 순환이 없는 그래프(DAG) 로 바꾸어 위상정렬이 가능해지는 구조다.

SCC 탐색을 위한 Tarjan 알고리즘

DFS 기반으로 SCC를 찾는 알고리즘

  • 각 노드에 index(DFS 방문 순서)와 lowlink(도달 가능한 최소 index)를 기록한다.
  • DFS 중 “되돌아갈 수 있는 가장 빠른 노드”를 추적하여 싸이클을 찾는다.
  • index == lowlink인 노드를 SCC 루트로 판단하고 스택에서 pop하여 하나의 컴포넌트로 묶는다.
  • 이 과정을 통해 전체 그래프가 SCC 단위로 그룹화된다.

싸이클 내부(SCC 내부) 평가는 DFS

의존성 그래프 만들 때 DFS를 사용한 것은 자료구조를 만들기 위함이었지만,
싸이클 내부를 평가(실행)할 때도 DFS를 사용한다.

SCC로 묶인 모듈들은 서로가 서로를 import하고 있어, 정확한 “먼저 실행해야 하는 모듈”을 고를 수 없다.

A → B
B → A

둘 다 먼저 초기화될 수 없기 때문에, SCC 내부 평가에서 DFS는 단순히 깊이 우선 탐색을 하는 것이 아니라, 무한 루프를 막고 올바른 초기화 흐름을 유지하기 위한 제어 로직과 함께 작동한다.

  • 방문 상태를 기록하여 무한 루프를 방지한다
    • 어떤 모듈이 이미 “평가 중”이라면, 다시 들어가지 않는다.
    • 이 시점의 상태를 “마스킹”하여 관리한다.
  • 이미 완전히 평가된 모듈은 다시 평가하지 않는다
    • 방문 기록이 있기 때문에 재실행은 일어나지 않는다.

이런 방식으로 DFS는 “순환 구간 안에서 가능한 만큼 안전하게 초기화를 진행하는 역할”을 한다.

라이브/정적 바인딩(Live Binding)이 왜 중요한가

ESM에서 import/export는 값 복사가 아니라 참조로 연결된다. 즉, 다음과 같은 상황이 가능하다.

  • A가 B의 변수를 import했는데
  • B가 아직 완전히 초기화되지 않은 상태여도
  • 참조 자체는 이미 연결되어 있기 때문에
  • B가 나중에 값을 넣으면 A에서 그 값을 정상적으로 볼 수 있다

이 특성 덕분에 순환 평가 과정에서 “아직 초기화되지 않은 값”이 있어도 전체 프로그램이 깨지지 않는다.

즉, DFS + partial evaluation은 실행 순서를 안전하게 관리하고 Live Binding은 아직 값이 준비되어 있지 않아도 참조 자체를 보존한다 이 두 가지가 결합되어 ESM은 순환 참조를 안전하게 처리할 수 있게 된다.

싸이클 처리 예시

// main.js
import './a.mjs';
import './b.mjs';

console.log('[main.js] done');

// a.mjs
import { valueB } from './b.mjs';

console.log('[a.js] 처음 실행 시 valueB:', valueB);
export const valueA = 'A_VALUE';
console.log('[a.js] valueA 초기화 완료');

// b.mjs
import { valueA } from './a.mjs';

console.log('[b.js] 처음 실행 시 valueA:', valueA);
export const valueB = 'B_VALUE';
console.log('[b.js] valueB 초기화 완료');

이때 로깅은 아래와 같이 찍힌다.

[b.js] 처음 실행 시 valueA: undefined
[b.js] valueB 초기화 완료
[a.js] 처음 실행 시 valueB: B_VALUE
[a.js] valueA 초기화 완료
[main.js] done

이제 순서대로 살펴보자

Parsing 단계를 거쳐서 Linking 단계에 진입하면
각 모듈 export 값이 아직 만들어지지 않았지만, 참조 슬롯(메모리 셀) 은 이미 만들어진 상태:

a.js: valueA → <uninitialized cell>
b.js: valueB → <uninitialized cell>

  1. 브라우저가 a.js 를 평가하려고 하면

    a.js 안에서 다시 b.js 를 import하고 있으므로 b.js 평가로 내려간다.

  2. b.js 가 평가되기 시작했는데,

    a.mjs를 import하지만, 이미 방문했던 노드이므로 스킵하고
    valueA를 가져온다. 이때 a.js는 아직 “부분 초기화 상태” 이다.
    따라서 undefined가 로깅된다.

    [b.js] 처음 실행 시 valueA: undefined

  3. b.js 의 export 평가

    이제 b.js의 export가 평가되어 실제 값으로 채워지고 아래가 로깅된다.

    [b.js] valueB 초기화 완료

  4. 다시 a.js로 돌아옴

    a.js의 다음 순서인 console.log가 실행되는데 이때는 b.mjs가 초기화되어 value가 존재한다.

    [a.js] 처음 실행 시 valueB: B_VALUE

    이후에 export 구문이 평가되고 마지막 콘솔이 찍힌다.

    [a.js] valueA 초기화 완료

정리하자면,

ESM이 순환에서도 무한 루프 없이 동작하는 이유는 다음 두 가지 때문이다.

  • 정적 바인딩(live binding)

    • 값 복사가 아니라 참조로 연결된다.
    • 초기화가 끝나지 않아도 참조는 유지된다.

  • SCC + 위상정렬 + partial evaluation

    • 순환 구간을 묶어 처리하고
    • 전체 그래프는 위상정렬로 실행 순서를 만든다.

하지만..

서로가 서로를 참조해야 한다는 것은 결합도가 높다는 의미로, 기능이 제대로 분리되지 않았을 가능성이 크다. ESM이 처리해준다고 해서 순환 구조를 그대로 두는 것은 바람직하지 않다.